GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Stable Marriage Problem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Stable Marriage Problem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">In der <a href="Mathematik" title="Mathematik">Mathematik</a>, der <a href="Volkswirtschaftslehre" title="Volkswirtschaftslehre">Volkswirtschaftslehre</a> und der <a href="Informatik" title="Informatik">Informatik</a> bezeichnet das Stable Marriage Problem (auch Stable Matching Problem, englisch für: Problem der stabilen Paarung, abgekürzt „SMP“) das Problem, eine stabile Paarung zwischen den Elementen zweier gleich großer Mengen zu finden. Dabei haben alle Elemente beider Mengen eine eindeutige Reihenfolge der Präferenz für jedes Element der anderen Menge.

Eine Paarung (oder ein Matching) ist eine Zuordnung der Elemente der einen Menge zu den Elementen der anderen Menge. Sie ist nicht stabil, wenn

<ul><li>ein Element A aus der ersten Menge ein Element B aus der zweiten Menge gegenüber dem Element der zweiten Menge bevorzugt, mit dem A aktuell gematcht ist, und</li>

<li>B ebenfalls A gegenüber dem Element aus der ersten Menge präferiert, mit dem B aktuell gematcht ist.</li></ul>

Mit anderen Worten: Eine Paarung ist stabil, wenn kein Match (A, B) existiert, den sowohl A als auch B im Vergleich zu ihrem jeweiligen aktuellen Match präferieren würden.

Das Stable Marriage Problem nimmt <a href="Heterosexualit%C3%A4t" title="Heterosexualität">heterosexuelle</a> Paare an und wurde wie folgt formuliert:

„n Männer und n Frauen, von denen jede Person alle Angehörigen des anderen Geschlechts in der Reihenfolge ihrer Präferenz angeordnet hat, sollen so <a href="Ehe" title="Ehe">verheiratet</a> werden, dass es keine zwei Menschen unterschiedlichen Geschlechts gibt, die beide lieber einander geheiratet hätten als ihre gegenwärtigen Partner. Wenn es keine solchen Paare gibt, gilt die Menge der Ehen als stabil.“

</blockquote>

</div></div>

Vom <a href="Stable_Roommates_Problem" title="Stable Roommates Problem">Stable Roommates Problem</a> unterscheidet sich das Stable Marriage Problem, weil es hier zwei verschiedene Mengen gibt (in diesem Beispiel Männer und Frauen), deren Elemente paarweise kombiniert werden müssen.

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

Algorithmen zur Lösung des Stable Marriage Problem lassen sich in vielen Praxissituationen anwenden. Dabei ist die Zuweisung von Medizinabsolventen zur <a href="%C3%84rztliche_Weiterbildung" class="mw-redirect" title="Ärztliche Weiterbildung">ärztlichen Weiterbildung</a> im Krankenhaus in den USA vielleicht die bekannteste. Im Jahr 2012 erhielten <a href="Lloyd_Shapley" class="mw-redirect" title="Lloyd Shapley">Lloyd Shapley</a> und <a href="Alvin_E._Roth" title="Alvin E. Roth">Alvin E. Roth</a> den <a href="Nobelpreis_f%C3%BCr_Wirtschaftswissenschaften" class="mw-redirect" title="Nobelpreis für Wirtschaftswissenschaften">Nobelpreis für Wirtschaftswissenschaften</a> „für die Theorie stabiler Allokationen und die Anwendung des Marktdesigns“.<a href="#cite_note-1">[1]</a>

Eine wichtige Anwendung von Stable Marriage im großen Rahmen ist die Zuweisung von Nutzern zu <a href="Server" title="Server">Servern</a> bei einem großen verteilten Internetdienst.<a href="#cite_note-nuggets-2">[2]</a> Milliarden von Nutzern rufen Webseiten, Videos und andere Dienste im Internet auf. Dabei muss jeder Nutzer zu einem von (potenziell) hunderttausenden Servern auf der ganzen Welt gematcht werden, die diesen Dienst anbieten. Ein Nutzer bevorzugt solche Server, die in hinreichender Nähe sind, um eine schnellere Antwortzeit für den gewünschten Dienst zu ermöglichen. Das führt zu einer (partiellen) Präferenzordnung der Server für jeden Nutzer. Jeder Server wiederum bevorzugt Nutzer, derer Bedienung wenig kostet, sodass sich eine (partielle) Präferenzordnung der Nutzer für jeden Server ergibt. <a href="Content_Delivery_Network" title="Content Delivery Network">Content Delivery Networks</a>, die einen großen Teil der weltweiten Inhalte und Dienste verteilen, lösen dieses große und komplexe Stable Marriage Problem zwischen Nutzern und Servern alle Zehntelsekunden. Damit ermöglichen sie Milliarden von Nutzern, mit den jeweiligen Servern gematcht zu werden, die ihre gewünschten <a href="Webseite" title="Webseite">Webseiten</a>, Videos oder anderen Dienste zur Verfügung stellen.<a href="#cite_note-nuggets-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Gale-Shapley-Algorithmus">Gale-Shapley-Algorithmus</h2></div>

Im Jahr 1962 bewiesen <a href="David_Gale_(%C3%96konom)" title="David Gale (Ökonom)">David Gale</a> und Lloyd Shapley, dass es für eine gleiche Anzahl an Männern und Frauen immer möglich ist, das Stable Marriage Problem zu lösen, sodass alle Ehen stabil sind. Sie präsentierten dafür einen <a href="Algorithmus" title="Algorithmus">Algorithmus</a>.<a href="#cite_note-gale-3">[3]</a><a href="#cite_note-4">[4]</a>

Der Gale-Shapley-Algorithmus enthält eine gewisse Anzahl von „Runden“ oder „<a href="Iteration" title="Iteration">Iterationen</a>“:

<ul><li>In der ersten Runde macht zuerst</li></ul>

<dl><dd>a) jeder nicht-<a href="Verlobung" title="Verlobung">verlobte</a> Mann derjenigen Frau, die ihm am besten gefällt, einen Heiratsantrag, und dann</dd>

<dd>b) antwortet jede Frau dem Verehrer, der ihr am besten gefällt, mit „vielleicht“ und allen anderen mit „nein“. Damit ist sie vorläufig mit dem Verehrer verlobt, der ihr bis dahin am besten gefällt, und dieser Verehrer ist entsprechend vorläufig mit ihr verlobt.</dd></dl>

<ul><li>In jeder folgenden Runde macht zuerst</li></ul>

<dl><dd>a) jeder nicht-verlobte Mann derjenigen Frau einen Antrag, die ihm am besten gefällt und der er noch keinen Antrag gemacht hat (unabhängig davon, ob diese Frau schon verlobt ist).</dd>

<dd>b) Dann antwortet jede Frau „vielleicht“, wenn sie gerade nicht verlobt ist oder wenn sie diesen Mann gegenüber ihrem gegenwärtigen vorläufigen Partner bevorzugt (in diesem Fall weist sie ihren gegenwärtigen vorläufigen Partner zurück und löst die Verlobung auf). Dadurch, dass Verlobungen vorläufig sind, behält eine schon verlobte Frau das Recht, ihren bis-dato-Partner sitzenzulassen und durch einen besseren zu ersetzen.</dd></dl>

<ul><li>Dieser Vorgang wird so lange wiederholt, bis jeder verlobt ist.</li></ul>

Die <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Laufzeitkomplexität</a> dieses Algorithmus ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> die Anzahl der Männer oder Frauen ist.<a href="#cite_note-IwamaMiyazaki2008-5">[5]</a>

Dieser Algorithmus garantiert, dass

<dl><dt>Jeder heiratet</dt>

<dd>Am Ende kann es keinen Mann und keine Frau geben, die beide nicht verlobt sind. Das liegt daran, dass er ihr irgendwann einen Antrag gemacht haben muss (denn ein Mann wird schließlich jeder Frau einen Antrag machen, wenn dies nötig sein sollte). Und sobald sie einen Antrag erhält, wäre sie daraufhin notwendigerweise (mit irgendjemandem) verlobt.</dd>

<dt>Die Ehen stabil sind</dt>

<dd><a href="Alice_und_Bob" title="Alice und Bob">Alice und Bob</a> seien beide verlobt, aber nicht miteinander. Nach Beendigung des Algorithmus ist es nicht möglich, dass sowohl Alice als auch Bob einander gegenüber ihren jeweiligen derzeitigen Partnern vorziehen. Wenn Bob Alice seiner gegenwärtigen Partnerin vorzieht, muss er Alice vor dieser einen Antrag gemacht haben. Wenn Alice seinen Antrag angenommen hat, aber schlussendlich nicht mit ihm verheiratet ist, muss sie ihn für jemanden, den sie mehr mag, verlassen haben. Daher kann sie Bob nicht mehr mögen als ihren gegenwärtigen Partner. Wenn Alice seinen Antrag abgelehnt hat, war sie bereits mit jemandem verlobt, den sie mehr mochte als Bob.</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Algorithmus">Algorithmus</h3></div>

<pre>function stableMatching {

Initialisiere alle m ∈ M und w ∈ W als alleinstehend

while ∃ Mann m, der noch einer Frau w einen Antrag machen kann alleinstehend {

w = erste Frau auf m’s Liste, der m noch keinen Antrag gemacht hat

if w ist alleinstehend

(m, w) sind verlobt

else gibt es schon ein Paar (m', w)

if w m gegenüber m' bevorzugt

m' wird alleinstehend

(m, w) sind verlobt

else

(m', w) bleiben verlobt

}

</pre>

<div class="mw-heading mw-heading3"><h3 id="Optimalität_der_Lösung">Optimalität der Lösung</h3></div>

Während die Lösung stabil ist, ist sie nicht notwendigerweise auch aus Sicht aller Individuen <a href="Optimierungsproblem" title="Optimierungsproblem">optimal</a>. Die traditionelle Form des Algorithmus ist optimal für die Gruppe, die die Anträge macht. Diese stabile und für die Antragsteller optimale Lösung muss jedoch nicht optimal für die Antragempfänger sein. Das zeigt folgendes Beispiel:

Es gibt drei Antragsteller (A,B,C) und drei Antragempfänger (X,Y,Z), die folgende Präferenzen haben:

Es gibt drei stabile Lösungen für diese Matchinganordnung:

<dl><dd>Die Antragsteller erhalten ihre erste Wahl und die Antragempfänger ihre dritte (AY, BZ, CX)</dd>

<dd>Alle Teilnehmer erhalten ihre zweite Wahl (AX, BY, CZ)</dd>

<dd>Die Antragempfänger erhalten ihre erste Wahl und die Antragsteller ihre dritte (AZ, BX, CY)</dd></dl>

Alle drei Lösungen sind stabil, weil Instabilität erfordert, dass beide Teilnehmer mit einem anderen Partner glücklicher wären. Wenn eine Gruppe ihre erste Wahl erhält, garantiert dies, dass die Matches stabil sind, weil Gruppenmitglieder mit jedem anderen vorgeschlagenen Match unglücklicher würden. Wenn jeder seine zweite Wahl erhält, ist garantiert, dass jedes andere Match einer der beiden Parteien missfallen wird. Der Algorithmus <a href="Grenzwert_(Funktion)" title="Grenzwert (Funktion)">konvergiert</a> in einer einzigen Runde zur Antragsteller-optimalen Lösung, weil jeder Antragempfänger genau einen Antrag erhält und daher diesen Antrag als beste Wahl auswählt. Damit ist garantiert, dass der Antrag jedes Antragstellers angenommen wird, womit das Match endet. Diese <a href="Asymmetrie" title="Asymmetrie">Asymmetrie</a> der Optimalität ist der Tatsache geschuldet, dass die Antragsteller aus der gesamten Menge wählen können, die Antragempfänger aber zu jedem Zeitpunkt aus einer begrenzten <a href="Teilmenge" title="Teilmenge">Teilmenge</a> der Antragsteller wählen.

<div class="mw-heading mw-heading2"><h2 id="Stable_Marriage_mit_Indifferenz">Stable Marriage mit Indifferenz</h2></div>

In der klassischen Version des Problems muss jede Person die Angehörigen des anderen Geschlechts in einer strikten Präferenzordnung anordnen. In der Praxis kann eine Person allerdings zwei oder mehr Personen im gleichen Maße favorisieren. Eine solche unentschiedene Präferenz wird als Indifferenz bezeichnet. Im folgenden Beispiel ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"> unentschieden zwischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{3}\&w_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{3}\&w_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8eceb6a469ae4f91642d76b5581873bfd49cfee4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.245ex; height:2.509ex;" alt="{\displaystyle w_{3}\&w_{1}}" loading="lazy">, und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8998e0957bb573a19e7d9d934ced62ee68ab8fb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{2}}" loading="lazy"> ist unentschieden zwischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}\&m_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}\&m_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/975874596c52abaf50245561bc5712bf16a3fe7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.997ex; height:2.509ex;" alt="{\displaystyle m_{1}\&m_{2}}" loading="lazy">.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4794614fbc3d6c4334522ade66a303115a3fead.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.968ex; height:2.843ex;" alt="{\displaystyle m_{1}[\ w_{2}\ w_{1}\ w_{3}\ ]\ \ \ \ \ \ w_{1}[\ m_{3}\ m_{2}\ m_{1}\ ]}" loading="lazy">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{2}[\left(w_{3}\ w_{1}\right)w_{2}]\ \ \ \ \ \ w_{2}[\left(m_{1}\ m_{2}\right)m_{3}]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83f830acc41778880a04f789a68d89df4ccd4b88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.877ex; height:2.843ex;" alt="{\displaystyle m_{2}[\left(w_{3}\ w_{1}\right)w_{2}]\ \ \ \ \ \ w_{2}[\left(m_{1}\ m_{2}\right)m_{3}]}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e391bb80a6228d73739501034d81b3b0ef41f1c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.968ex; height:2.843ex;" alt="{\displaystyle m_{3}[\ w_{1}\ w_{2}\ w_{3}\ ]\ \ \ \ \ \ w_{3}[\ m_{2}\ m_{3}\ m_{1}\ ]}" loading="lazy">

Wenn unentschiedene Präferenzlisten zugelassen sind, hat das Stable Marriage Problem drei <a href="Stabilit%C3%A4t_(Sortierverfahren)" title="Stabilität (Sortierverfahren)">Stabilitätskonzepte</a>, die in den folgenden Abschnitten behandelt werden.

Ein Matching wird als schwach stabil bezeichnet, sofern es kein Paar gibt, sodass jeder von beiden den anderen strikt gegenüber seinem/ihren Matchingpartner bevorzugt. Robert W. Irving<a href="#cite_note-sciencedirect-6">[6]</a> hat den Gale-Shapley-Algorithmus wie folgt erweitert, um so ein schwach stabiles Matching zum Zeitpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"> zu liefern, wobei n die Größe des Stable Marriage Problem bezeichnet. Wenn die Männer und Frauen in ihren Präferenzen indifferent sind, wird willkürlich entschieden. Mit dem Fortschreiten des Algorithmus werden die Präferenzlisten immer kürzer.

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr mw-highlight-lines" dir="ltr"><pre>Ordne jede Person als alleinstehend ein;

while (irgendein Mann m alleinstehend ist) do

begin

w := erste Frau auf m's Liste;

m macht einen Antrag und verlobt sich mit w;

if (irgendein Mann m' mit w verlobt ist) then

ordne m' als alleinstehend ein;

for each (Nachfolger m'' von m auf w's Liste) do

delete das Paar (m'', w)

end;

gib die verlobten Paare aus, die ein stabiles Matching bilden

</pre></div>

Ein Matching ist super-stabil, wenn es kein Paar gibt, sodass jeder von beiden den anderen strikt gegenüber seinem/ihrem Partner bevorzugt oder zwischen ihnen indifferent ist. Robert W. Irving<a href="#cite_note-sciencedirect-6">[6]</a> hat den oben beschriebenen Algorithmus modifiziert, um zu überprüfen, ob es ein solches super-stabiles Matching gibt und, falls dieses existiert, das Matching zum Zeitpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"> ausgibt. Im Folgenden der <a href="Pseudocode" title="Pseudocode">Pseudo-Code</a>:

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr mw-highlight-lines" dir="ltr"><pre>Ordne jede Person als alleinstehend ein;

repeat

while (irgendein Mann m alleinstehend ist) do

for each (Frau w am Anfang von m's Liste) do

begin

m macht einen Antrag und verlobt sich mit w;

for each (strikten Nachfolger m' von m auf w's Liste) do

begin

if (m' ist verlobt) mit w then

break die Verlobung;

delete the pair (m'. w)

end

end

for each (woman w who is multiply engaged) do

begin

break all engagements involving W;

for each (man m at the tail of w’s list) do

delete the pair (m. w)

end;

until (some man’s list is empty) or (jeder verlobt ist);

if jeder verlobt ist, then

ist die Verlobungsrelation ein super-stabiles Matching

else

existiert kein super-stabiles Matching

</pre></div>

Ein Matching ist stark stabil, wenn es kein Paar x, y gibt, sodass x y strikt gegenüber seinem/ihrem Partner bevorzugt und y entweder x strikt gegenüber seinem/ihrem Partner bevorzugt oder indifferent zwischen beiden ist. Robert W. Irving<a href="#cite_note-sciencedirect-6">[6]</a> hat einen Algorithmus entwickelt, der überprüft, ob so ein stark stabiles Matching existiert und, wenn es existiert, das Matching ausgibt. Der Algorithmus berechnet das perfekte Matching zwischen Mengen von Männern und Frauen, sodass er die kritische Menge an Männern findet, die mit mehreren Frauen verlobt sind. Da solche Verlobungen niemals stabil sind, werden alle solchen Paare gelöscht, und der Antragsprozess wird wiederholt, bis entweder 1) die Präferenzliste irgendeines Mannes leer wird (in diesem Fall gibt es kein stark stabiles Matching) oder 2) ein stark stabiles Matching erreicht wird. Hier der Pseudo-Code, um ein stark stabiles Matching zu finden. Es hat eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{4})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{4})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ae98b94e039c8eafabf6fe6a0128d232ed7d21f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{4})}" loading="lazy">, was im Lemma 4.6 erklärt wird.<a href="#cite_note-sciencedirect-6">[6]</a>

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr mw-highlight-lines" dir="ltr"><pre>Ordne jede Person als alleinstehend ein;

repeat

while (irgendein Mann alleinstehend ist) do

for each (Frau w am Anfang von m's Liste) do

begin

m macht einen Antrag und verlobt sich mit w;

for each (strikten Nachfolger m' von m auf w's Liste) do

begin

if (m' verlobt ist) mit w then

break die Verlobung;

delete das Paar (m'. w)

end

end

if (die Verlobungsrelation kein perfektes Matching enthält) then

begin

finde die kritische Menge Z an Männern;

for each (Frau w die mit einem Mann aus Z verlobt ist) do

begin

break alle Verlobungen von w;

for each Mann m am Ende von w's Liste do

delete das Paar (m, w)

end;

end;

until (die Liste eines Mannes leer ist) or (jeder verlobt ist);

if jeder verlobt ist then

ist die Verlobungsrelation ein super-stabiles Matching

else

existiert kein stark-stabiles Matching

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Ähnliche_Probleme">Ähnliche Probleme</h2></div>

Das <a href="Zuordnungsproblem" title="Zuordnungsproblem">Zuordnungsproblem</a> versucht, in einem gewichteten zweiteiligen Graphen ein Matching mit maximaler Gewichtung zu finden. Maximal gewichtete Matchings müssen nicht stabil sein, aber in manchen Anwendungen ist ein maximal gewichtetes Matching besser als ein stabiles.

Das Stable Roommates Problem ist ähnlich wie das Stable Marriage Problem, aber es unterscheidet sich insofern davon, dass alle Teilnehmer einer einzigen Gruppe angehören (anstatt zu gleichen Teilen in „Männer“ und „Frauen“ getrennt zu sein).

Das Krankenhäuser/Assistenzärzte-Problem – auch bekannt als das Hochschulzulassungsproblem – unterscheidet sich vom Stable Marriage Problem insofern, dass ein Krankenhaus mehrere Assistenzärzte aufnehmen kann. Ebenso kann eine Hochschule mehr als einen Studenten in einem Jahrgang haben. Algorithmen zur Lösung des Krankenhäuser/Assistenzärzte-Problems können krankenhausorientiert sein (wie es das <a href="NRMP" class="mw-redirect" title="NRMP">NRMP</a> vor 1995 war)<a href="#cite_note-Robinson-7">[7]</a>, oder ärzteorientiert. Dieses Problem wurde mit einem Algorithmus aus dem gleichen originalen Paper von Gale und Shapley gelöst, in dem auch das Stable Marriage Problem gelöst wurde.<a href="#cite_note-gale-3">[3]</a>

Das Krankenhäuser/Assistenzärzte-Problem mit Paaren ermöglicht es, dass die Menge der Assistenzärzte Paare enthält, die zusammen zugewiesen werden müssen – entweder zum gleichen Krankenhaus oder zu zwei konkreten Krankenhäusern, die das Paar ausgewählt hat. Damit will beispielsweise ein Ehepaar sichergehen, dass beide Partner zusammen bleiben und nicht in Ausbildungsprogrammen landen, die weit voneinander entfernt sind. Das Hinzufügen von Paaren zum Krankenhäuser/Assistenzärzte-Problem macht das Problem <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>.<a href="#cite_note-8">[8]</a>

Das Matching Problem mit Verträgen stellt eine Generalisierung des Matchingproblems dar, in dem Teilnehmer mit verschiedenen Vertragsbedingungen gematcht werden können.<a href="#cite_note-9">[9]</a> Ein wichtiger Spezialfall ist dabei das Matching mit flexiblen Löhnen.<a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Implementierung_in_Softwarepaketen">Implementierung in Softwarepaketen</h2></div>

<ul><li><a href="R_(Programmiersprache)" title="R (Programmiersprache)">R</a>: Der Gale–Shapley-Algorithm (auch als Deferred-Acceptance-Algorithmus bezeichnet) für das Stable Marriage Problem und das Krankenhäuser/Assistenzärzte-Problem ist im Paket <code>matchingMarkets</code><a href="#cite_note-11">[11]</a><a href="#cite_note-12">[12]</a> implementiert.</li></ul>

<ul><li><a href="Python_(Programmiersprache)" title="Python (Programmiersprache)">Python</a>: Der Gale-Shapley-Algorithmus ist gemeinsam mit einigen anderen Algorithmen für generalisierte Matchingprobleme im Paket <code>QuantEcon/MatchingMarkets.py</code> enthalten.<a href="#cite_note-13">[13]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Zuordnungsproblem" title="Zuordnungsproblem">Zuordnungsproblem</a> ein ähnliches Problem, bei dem die Gewichtungen der Graphenkanten austauschbar sind</li>

<li><a href="Stable_Roommates_Problem" title="Stable Roommates Problem">Stable Roommates Problem</a> ein ähnliches Problem, aber mit einer Menge der Größe n und Präferenzen der Anzahl n-1</li>

<li><a href="Nash-Gleichgewicht" title="Nash-Gleichgewicht">Nash-Gleichgewicht</a></li>

<li><a href="Ungarische_Methode" title="Ungarische Methode">Ungarische Methode</a> ein Algorithmus, um das gewichtete zweigeteilte Matchingproblem zu lösen</li>

<li><a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching (Graphentheorie)</a> generalized matching problem in graphs</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Lehrbücher_und_weitere_wichtige_Werke,_die_im_Text_nicht_zitiert_werden">Lehrbücher und weitere wichtige Werke, die im Text nicht zitiert werden</h3></div>

<ul><li>L. Dubins, D. Freedman: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Machiavelli and the Gale–Shapley algorithm</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">American Mathematical Monthly</cite>. 88. Jahrgang, Nr. 7, 1981, S. 485–494, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307/2321753">10.2307/2321753</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Machiavelli+and+the+Gale-Shapley+algorithm&rft.au=L.%26%2332%3BDubins%2C%26%2332%3BD.%26%2332%3BFreedman&rft.date=1981&rft.doi=10.2307%2F2321753&rft.genre=journal&rft.issue=7&rft.jtitle=American+Mathematical+Monthly&rft.pages=485-494&rft.volume=88.+Jahrgang" style="display:none"> </li>

<li>J. Kleinberg, E. Tardos (2005). Algorithm Design, Kapitel 1, pp 1–12. Siehe auch Begleit-Website für den Text <a rel="nofollow" class="external text" href="http://www.aw-bc.com/info/kleinberg/">aw-bc.com</a>.</li>

<li><a href="Donald_Knuth" class="mw-redirect" title="Donald Knuth">D. E. Knuth</a> (1976). Mariages stables. Montreal: Les Presses de l'Universite de Montreal.</li>

<li><a href="Donald_Knuth" class="mw-redirect" title="Donald Knuth">D. E. Knuth</a> (1996). Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, english translation, (CRM Proceedings and Lecture Notes), <a href="American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a>.</li>

<li>B. Pittel (1992). On likely solutions of a stable marriage problem, The Annals of Applied Probability 2; 358-401.</li>

<li>A. E. Roth (1984). The evolution of the labor market for medical interns and residents: A case study in game theory, <a href="Journal_of_Political_Economy" title="Journal of Political Economy">Journal of Political Economy</a> 92: 991–1016.</li>

<li>A. E. Roth, M. A. O. Sotomayor (1990). Two-sided matching: A study in game-theoretic modeling and analysis <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>.</li>

<li>Yoav Shoham, Kevin Leyton-Brown: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations</cite>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, New York 2009, ISBN 978-0-521-89943-7 (englisch, <a rel="nofollow" class="external text" href="http://www.masfoundations.org/">masfoundations.org</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.au=Yoav%26%2332%3BShoham%2C%26%2332%3BKevin%26%2332%3BLeyton-Brown&rft.btitle=Multiagent+Systems%3A+Algorithmic%2C+Game-Theoretic%2C+and+Logical+Foundations&rft.date=2009&rft.genre=book&rft.isbn=9780521899437&rft.place=New+York&rft.pub=Cambridge+University+Press" style="display:none">  Siehe Abschnitt 10.6.4; <a rel="nofollow" class="external text" href="http://www.masfoundations.org/download.html">downloadable free online</a>.</li>

<li>J. Schummer, R.V. Vohra: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Algorithmic Game Theory</cite>. 2007, ISBN 978-0-521-87282-9, Mechanism design without money, S. 255–262 (englisch, <a rel="nofollow" class="external text" href="http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf">cambridge.org</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Mechanism+design+without+money&rft.au=J.%26%2332%3BSchummer%2C%26%2332%3BR.V.%26%2332%3BVohra&rft.btitle=Algorithmic+Game+Theory&rft.date=2007&rft.genre=bookitem&rft.isbn=9780521872829&rft.pages=255-262" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP">National Resident Matching Program and related medical labor markets.</a> In: Al Roth's game theory, experimental economics, and market design page, harvard.edu (archiviert, englisch)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> <a rel="nofollow" class="external text" href="https://www.nobelprize.org/nobel_prizes/economics/laureates/2012/">The Prize in Economic Sciences 2012.</a> Nobelprize.org, abgerufen am 2. Januar 2018 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AStable+Marriage+Problem&rft.title=The+Prize+in+Economic+Sciences+2012&rft.description=The+Prize+in+Economic+Sciences+2012&rft.identifier=&rft.publisher=Nobelprize.org&rft.date=&rft.language=en">

</li>

<li id="cite_note-nuggets-2">↑ <a href="#cite_ref-nuggets_2-0">a</a> <a href="#cite_ref-nuggets_2-1">b</a> Bruce Maggs and Ramesh Sitaraman: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Algorithmic nuggets in content delivery</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">ACM SIGCOMM Computer Communication Review</cite>. 45. Jahrgang, Nr. 3, 2015 (englisch, <a rel="nofollow" class="external text" href="http://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf">sigcomm.org</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Algorithmic+nuggets+in+content+delivery&rft.au=Bruce+Maggs+and+Ramesh+Sitaraman&rft.date=2015&rft.genre=journal&rft.issue=3&rft.jtitle=ACM+SIGCOMM+Computer+Communication+Review&rft.volume=45.+Jahrgang" style="display:none">

</li>

<li id="cite_note-gale-3">↑ <a href="#cite_ref-gale_3-0">a</a> <a href="#cite_ref-gale_3-1">b</a> D. Gale, L. S. Shapley: <cite class="lang" lang="en" dir="auto" style="font-style:italic">College Admissions and the Stability of Marriage</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="American_Mathematical_Monthly" title="American Mathematical Monthly">American Mathematical Monthly</a></cite>. 69. Jahrgang, 1962, S. 9–14, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307/2312726">10.2307/2312726</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=College+Admissions+and+the+Stability+of+Marriage&rft.au=D.%26%2332%3BGale%2C%26%2332%3BL.+S.%26%2332%3BShapley&rft.btitle=American+Mathematical+Monthly&rft.date=1962&rft.doi=10.2307%2F2312726&rft.genre=book&rft.pages=9-14&rft.volume=69.+Jahrgang" style="display:none">

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Harry Mairson: The Stable Marriage Problem. In: The Brandeis Review, 12, 1992 (<a rel="nofollow" class="external text" href="http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html">cs.columbia.edu</a>).

</li>

<li id="cite_note-IwamaMiyazaki2008-5"><a href="#cite_ref-IwamaMiyazaki2008_5-0">↑</a> Kazuo Iwama, Shuichi Miyazaki: <cite class="lang" lang="en" dir="auto" style="font-style:italic">A Survey of the Stable Marriage Problem and Its Variants</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008)</cite>. 2008, S. 131–136, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109/ICKS.2008.7">10.1109/ICKS.2008.7</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=A+Survey+of+the+Stable+Marriage+Problem+and+Its+Variants&rft.au=Kazuo%26%2332%3BIwama%2C%26%2332%3BShuichi%26%2332%3BMiyazaki&rft.btitle=International+Conference+on+Informatics+Education+and+Research+for+Knowledge-Circulating+Society+%28icks+2008%29&rft.date=2008&rft.doi=10.1109%2FICKS.2008.7&rft.genre=book&rft.pages=131-136" style="display:none">

</li>

<li id="cite_note-sciencedirect-6">↑ <a href="#cite_ref-sciencedirect_6-0">a</a> <a href="#cite_ref-sciencedirect_6-1">b</a> <a href="#cite_ref-sciencedirect_6-2">c</a> <a href="#cite_ref-sciencedirect_6-3">d</a> Robert W. Irving: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Stable marriage and indifference</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Discrete Applied Mathematics</cite>. 48. Jahrgang, Nr. 3, 15. Februar 1994, S. 261–272, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016/0166-218X%2892%2900179-P">10.1016/0166-218X(92)00179-P</a> (englisch, <a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/0166218X9200179P">sciencedirect.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Stable+marriage+and+indifference&rft.au=Robert+W.%26%2332%3BIrving&rft.date=1994-02-15&rft.doi=10.1016%2F0166-218X%2892%2900179-P&rft.genre=journal&rft.issue=3&rft.jtitle=Discrete+Applied+Mathematics&rft.pages=261-272&rft.volume=48.+Jahrgang" style="display:none">

</li>

<li id="cite_note-Robinson-7"><a href="#cite_ref-Robinson_7-0">↑</a> Sara Robinson: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Are Medical Students Meeting Their (Best Possible) Match?</cite> In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">SIAM News</cite>. Nr. 3, April 2003, S. 36 (englisch, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf">siam.org</a> (<a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fwww.siam.org%2Fpdf%2Fnews%2F305.pdf">Originals</a> vom 18. November 2016 im <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>) [abgerufen am 2. Januar 2018]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Are+Medical+Students+Meeting+Their+%28Best+Possible%29+Match%3F&rft.au=Sara%26%2332%3BRobinson&rft.date=2003-04&rft.genre=journal&rft.issue=3&rft.jtitle=SIAM+News&rft.pages=36" style="display:none">

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> D. Gusfield, R. W. Irving: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The Stable Marriage Problem: Structure and Algorithms</cite>. MIT Press, 1989, ISBN 0-262-07118-5, S. 54 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.au=D.%26%2332%3BGusfield%2C%26%2332%3BR.+W.%26%2332%3BIrving&rft.btitle=The+Stable+Marriage+Problem%3A+Structure+and+Algorithms&rft.date=1989&rft.genre=book&rft.isbn=0262071185&rft.pages=54&rft.pub=MIT+Press" style="display:none">

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> John William Hatfield, Paul Milgrom: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Matching with Contracts</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="American_Economic_Review" class="mw-redirect" title="American Economic Review">American Economic Review</a></cite>. 95. Jahrgang, Nr. 4, 2005, S. 913–935, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1257/0002828054825466">10.1257/0002828054825466</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Matching+with+Contracts&rft.au=John+William%26%2332%3BHatfield%2C%26%2332%3BPaul%26%2332%3BMilgrom&rft.date=2005&rft.doi=10.1257%2F0002828054825466&rft.genre=journal&rft.issue=4&rft.jtitle=American+Economic+Review&rft.pages=913-935&rft.volume=95.+Jahrgang" style="display:none">

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> Vincent Crawford, Elsie Marie Knoer: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Job Matching with Heterogeneous Firms and Workers</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Econometrica" title="Econometrica">Econometrica</a></cite>. 49. Jahrgang, Nr. 2, 1981, S. 437–450, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307/1913320">10.2307/1913320</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Job+Matching+with+Heterogeneous+Firms+and+Workers&rft.au=Vincent%26%2332%3BCrawford%2C%26%2332%3BElsie+Marie%26%2332%3BKnoer&rft.date=1981&rft.doi=10.2307%2F1913320&rft.genre=journal&rft.issue=2&rft.jtitle=Econometrica&rft.pages=437-450&rft.volume=49.+Jahrgang" style="display:none">

</li>

<li id="cite_note-11"><a href="#cite_ref-11">↑</a> Thilo Klein: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Analysis of Stable Matchings in R: Package matchingMarkets</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Vignette to R Package matchingMarkets</cite>. 2015 (englisch, <a rel="nofollow" class="external text" href="http://cran.at.r-project.org/web/packages/matchingMarkets/vignettes/matching.pdf">r-project.org</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Stable+Marriage+Problem&rft.atitle=Analysis+of+Stable+Matchings+in+R%3A+Package+matchingMarkets&rft.au=Thilo%26%2332%3BKlein&rft.btitle=Vignette+to+R+Package+matchingMarkets&rft.date=2015&rft.genre=book" style="display:none">

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> <a rel="nofollow" class="external text" href="http://cran.at.r-project.org/web/packages/matchingMarkets/">matchingMarkets: Analysis of Stable Matchings.</a> In: R Project. Abgerufen im 1. Januar 1 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AStable+Marriage+Problem&rft.title=matchingMarkets%3A+Analysis+of+Stable+Matchings&rft.description=matchingMarkets%3A+Analysis+of+Stable+Matchings&rft.identifier=&rft.date=&rft.language=en">

</li>

<li id="cite_note-13"><a href="#cite_ref-13">↑</a> <a rel="nofollow" class="external text" href="https://github.com/QuantEcon/MatchingMarkets.py">matchingMarkets.py.</a> In: Python package. Abgerufen im 1. Januar 1 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AStable+Marriage+Problem&rft.title=matchingMarkets.py&rft.description=matchingMarkets.py&rft.identifier=&rft.date=&rft.language=en">

</li>

</ol></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-19" href="https://de.wikipedia.org/wiki/?title=Stable_Marriage_Problem&oldid=260725610">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>